//给你一个非负整数数组 nums 和一个整数 target 。 
//
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 
//
// 
// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 
// 
//
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1,1,1], target = 3
//输出：5
//解释：一共有 5 种方法让最终目标和为 3 。
//-1 + 1 + 1 + 1 + 1 = 3
//+1 - 1 + 1 + 1 + 1 = 3
//+1 + 1 - 1 + 1 + 1 = 3
//+1 + 1 + 1 - 1 + 1 = 3
//+1 + 1 + 1 + 1 - 1 = 3
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], target = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 1000 
// 0 <= sum(nums[i]) <= 1000 
// -1000 <= target <= 1000 
// 
//
// Related Topics 数组 动态规划 回溯 👍 1801 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//java:目标和
public class Q0494TargetSum {
    public static void main(String[] args){
        Solution solution = new Q0494TargetSum().new Solution();
        solution.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 转化为[0-1]背包问题，分成两部分，一部分posSum全是+，一部分negSum全是-，其中posSum = sum - negSum，总和=target
    public int findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length ==0 || nums.length > 20
        || target < -1000 || target > 1000) return -1;
        int sum = Arrays.stream(nums).sum();
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) return 0; // 特判
        int negSum = (sum - target) / 2;
        int n = nums.length;
        // dp[i][j] 表示前i个数字之和为j的方案数，求dp[n][negSum]
//        int[][] dp = new int[n + 1][negSum + 1];
//        // 注意 前0个和为0的方案应该有一个
//        dp[0][0] = 1;
//        for (int i = 1; i < n + 1; i++) {
//            // 注意j从0 开始，和为0的情况
//            for (int j = 0; j < negSum + 1; j++) {
//                // j < nums[i - 1] 必不能选，和肯定大于j
//                if (j < nums[i - 1]) dp[i][j] = dp[i - 1][j];
//                // 类似于斐波那契数列，求方案数的和
//                else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
//            }
//        }
//        return dp[n][negSum];
        int[] dp = new int[negSum + 1];
        dp[0] = 1;
        for (int i = 1; i < n + 1; i++) {
            for (int j = negSum; j >= 0; j--) {
                if (j >= nums[i - 1]) {
                    dp[j] = dp[j] + dp[j - nums[i - 1]];
                }
            }
        }
        return dp[negSum];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}